/*
 * @Author: wwssaabb
 * @Date: 2021-12-07 18:03:21
 * @LastEditTime: 2021-12-07 18:03:21
 * @FilePath: \handwritten-code\algorithm\合并两个有序数组.js
 */

/* 
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2， 另有两个整数 m 和 n， 分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中， 使合并后的数组同样按 非递减顺序 排列。

注意： 最终， 合并后数组不应由函数返回， 而是存储在数组 nums1 中。 为了应对这种情况， nums1 的初始长度为 m + n， 其中前 m 个元素表示应合并的元素， 后 n 个元素为 0， 应忽略。 nums2 的长度为 n。

示例 1：
输入： nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
输出：[1, 2, 2, 3, 5, 6]
解释： 需要合并[1, 2, 3] 和[2, 5, 6]。

来源： 力扣（ LeetCode）
链接： https: //leetcode-cn.com/problems/merge-sorted-array
*/

//逆向双指针，时间复杂度O(m+n)、空间复杂度O(1)
var merge = function (nums1, m, nums2, n) {
  let k = n + m - 1
  n--
  m--
  while (n >= 0 || m >= 0) {
    if (m < 0) {
      nums1[k--] = nums2[n--]
    } else if (n < 0) {
      nums1[k--] = nums1[m--]
    } else if (nums1[m] <= nums2[n]) {
      nums1[k--] = nums2[n--]
    } else {
      nums1[k--] = nums1[m--]
    }
  }
};